package pri.zjy.tree;

import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;
import java.util.Queue;

/**
 * @author zhangjy
 * @description 填充每个节点的下一个右侧节点指针
 * <p>
 * 进阶：
 * <p>
 * 你只能使用常量级额外空间。
 * 使用递归解题也符合要求，本题中递归程序占用的栈空间不算做额外的空间复杂度。
 * @date 2025/4/7 20:18
 */
public class Connect_116 {

    public static void main(String[] args) {

    }

    /**
     * 个解-DFS
     * <p>
     * 思路：记录本层层数，以及本层最新的一个前驱节点prev；每次更新prev的右指针next
     */
    public Node connect3(Node root) {
        dfs3(root, 0, new HashMap<Integer, Node>());
        return root;
    }

    public void dfs3(Node node, int level, Map<Integer, Node> levelPrevNodeMap) {
        if (node == null) return;

        Node prevNode = levelPrevNodeMap.get(level);
        // 记录前驱节点的next为当前节点
        if (prevNode != null) {
            prevNode.next = node;
        }
        // 更新本层的最新上一个节点
        levelPrevNodeMap.put(level, node);
        level++;

        // 先序遍历顺序递归下一层
        dfs3(node.left, level, levelPrevNodeMap);
        dfs3(node.right, level, levelPrevNodeMap);
    }

    /**
     * 官解-BFS
     * <p>
     * 思路：参照层序遍历，遍历每层节点，设置节点的next；每层首个、最后一个节点的next，都为null（题目说所有next指针初始为null），不用管；其它节点，可以利用队列特性，出队后队首元素会改变。
     * <p>
     * 复杂度，同个解的DFS。
     */
    public Node connect2(Node root) {
        if (root == null) return null;

        Queue<Node> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            int curLayerSize = queue.size();
            // 遍历这一层所有节点
            for (int i = 0; i < curLayerSize; i++) {
                Node poll = queue.poll();
                // 除本层最后一个节点外，给其它节点设置next
                if (i < curLayerSize - 1) {
                    // 所以对于根节点root来说，都不会进这个判断.
                    // 除root所在层的其它层，该层第一个节点，queue.poll()后，当前队列的队首元素就是其next。
                    // 对每层的最后一个节点来说，其next都为null，而Node初始化时next本就为null；
                    poll.next = queue.peek();
                }

                if (poll.left != null) queue.offer(poll.left);
                if (poll.right != null) queue.offer(poll.right);
            }
        }
        return root;
    }

    /**
     * 个解-BFS
     * <p>
     * 分析：题目已知，所有next指针初始为null
     * <p>
     * 时间复杂度：T(n) = O(n); 其中，n为节点个数，每个节点会被访问一次且只会被访问一次，即从队列中弹出。
     * 空间复杂度：S(n) = O(n); 其中，这是一棵完美二叉树，它的最后一个层级包含 N/2 个节点。广度优先遍历的复杂度取决于一个层级上的最大元素数量。这种情况下空间复杂度为 O(N)。
     */
    public Node connect(Node root) {
        if (root == null) return null;

        Queue<Node> queue = new LinkedList<>();
        queue.offer(root);
        Node curLayerPrevNode = null;
        while (!queue.isEmpty()) {
            int curLayerSize = queue.size();
            // 遍历这一层所有节点
            for (int i = 0; i < curLayerSize; i++) {
                Node poll = queue.poll();
                // 除本层第一个节点，其它都要设置其前驱的next
                if (i != 0) {
                    curLayerPrevNode.next = poll;
                    // 设置最后一个节点的next为空
                    if (i == curLayerSize - 1) {
                        poll.next = null;
                    }
                }
                // 更新前驱节点
                curLayerPrevNode = poll;

                if (poll.left != null) queue.offer(poll.left);
                if (poll.right != null) queue.offer(poll.right);
            }
        }
        return root;
    }

    class Node {

        public int val;

        public Node left;

        public Node right;

        public Node next;

        public Node() {
        }

        public Node(int _val) {
            val = _val;
        }

        public Node(int _val, Node _left, Node _right, Node _next) {
            val = _val;
            left = _left;
            right = _right;
            next = _next;
        }

    }

}
